#define _CRT_SECURE_NO_WARNINGS 1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    long long kthLargestLevelSum(TreeNode* root, int k) {
        queue<TreeNode*> qu;
        priority_queue<long long, vector<long long>, greater<long long>> ret;
        qu.push(root);
        while (!qu.empty())
        {
            int n = qu.size();
            long long maxVal = 0;
            while (n--)
            {
                maxVal += qu.front()->val;
                TreeNode* le = qu.front()->left;
                TreeNode* ri = qu.front()->right;
                qu.pop();
                if (le) qu.push(le);
                if (ri) qu.push(ri);
            }
            ret.push(maxVal);
            if (ret.size() > k) ret.pop();
        }

        if (k > ret.size()) return -1;

        return ret.top();
    }
};